//
//  SlidingWindows.hpp
//  labuladong
//
//  Created by 刘振舟 on 2024/2/4.
//

#ifndef SlidingWindows.hpp
#define SlidingWindows.hpp
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> window, need;
        for (char c: t) {
            need[c]++;
        }
        int left = 0, right = 0, valid = 0;
        int start = 0, len = INT_MAX;
        
        while (right < s.size()) {
            char ch = s[right++];
            if (need.count(ch)) {
                ++window[ch];
                if (window[ch] == need[ch]) {
                    ++valid;
                }
            }
            
            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char leftChar = s[left++];
                if (need.count(leftChar)) {
                    if (window[leftChar] == need[leftChar]) {
                        --valid;
                    }
                    window[leftChar]--;
                }
            }
            
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
    
    
    bool checkInclusion(string s1, string s2) {
        unordered_map<char, int> window, need;
        for (char ch : s1) {
            need[ch]++;
        }
        int left = 0, right = 0, valid = 0;
        while (right < s2.length()) {
            char c = s2[right++];
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) {
                    ++valid;
                }
            }
            
            while (right - left >= s1.size()) {
                if (valid == need.size()) {
                    return true;
                }
                char ch = s2[left++];
                if (need.count(ch)) {
                    if (window[ch] == need[ch]) {
                        --valid;
                    }
                    window[ch]--;
                }
            }
        }
        return false;
    }
    
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> window, need;
        for (char ch : p) {
            need[ch]++;
        }
        int left = 0, right = 0, valid = 0;
        vector<int> res;
        while (right < s.length()) {
            char c = s[right++];
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) {
                    ++valid;
                }
            }
            
            while (right - left >= p.size()) {
                if (valid == need.size()) {
                    res.push_back(left);
                }
                char ch = s[left++];
                if (need.count(ch)) {
                    if (window[ch] == need[ch]) {
                        --valid;
                    }
                    window[ch]--;
                }
            }
        }
        return res;
        }
    
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
        int left = 0, right = 0, res = 0;
        while (right < s.size()) {
            char c = s[right];
            map[c]++;
            while (map[c] > 1) {
                char ch = s[left];
                ++left;
                map[ch]--;
            }
            ++right;
            res = max(res, right - left);
        }
        return res;
    }
};

#endif /* SlidingWindows.hpp
*/
